#include<iostream>
#include<fstream>
#include<stack>
#include<string>
#include<queue>
using namespace std;

class MapMatrix
{
public:
    char * mVexs;
    int mVexNum;
    int mEdgNum;
    int **mMatrix;
    MapMatrix(int num);
    int GetPos(char Character);
    void Insert(string address);
    ~MapMatrix();
    void DFSsearch();
    void DFSRsearch(int i, int * visit);
    void BFSsearch();
    void BFSRsearch(int i, int * visit);
};

MapMatrix::MapMatrix(int num)
{
    mVexs = new char[num];
    mMatrix = new int*[num];
    mEdgNum = 0;
    
    for (int i = 0; i < num; i++)
    {
        mMatrix[i] = new int[num];
    }
    
    for(int i = 0;i<num;i++)
    {
        for(int j = 0;j<num;j++)
        {
            
            if(mMatrix[i][j]!=0)
            {
                mEdgNum++;
            }
        }
    }
    
    mVexNum = num;
    
}

MapMatrix::~MapMatrix()
{
    for(int i = 0;i<mVexNum;i++)
    {
        delete[] mMatrix[i];
    }
    delete[] mMatrix;
}

void MapMatrix::Insert(string address)
{
    fstream file;
    file.open(address);
    for (int i = 0; i < mVexNum;i++)
    {
        file >> mVexs[i];
    }
    for (int i = 0; i < mVexNum;i++)
    {
        for (int j = 0; j < mVexNum;j++)
        {
            file >> mMatrix[i][j];
        }
    }
    for (int i = 0; i < mVexNum;i++)
    {
        cout<< mVexs[i]<<" ";
    }
    cout << endl;
    for (int i = 0; i < mVexNum; i++)
    {
        for (int j = 0; j < mVexNum;j++)
        {
            cout<< mMatrix[i][j]<<" ";
            
        }
        cout << endl;
    }
    file.close();
}

void MapMatrix::DFSsearch()
{
    int i;
    int visited[mVexNum];

    for (i = 0; i < mVexNum;i++)
    {
        visited[i] = 0;
    }
    cout << "进行DFS递归查找: ";
    for (i = 0; i < mVexNum;i++)
    {
        if(!visited[i])
        {
            DFSRsearch(i, visited);
            
        }
    }
    cout << endl;
    for (i = 0; i < mVexNum;i++)
    {
        visited[i] = 0;
        
    }
    //getchar();
    cout << "进行DFS非递归查找：";
    stack<int> stackForSearch;
    
    for (int k = 0; k < mVexNum; k++)
    {
        if(!visited[k])
        {
             stackForSearch.push(k);
            while(!stackForSearch.empty())
            {
                i = stackForSearch.top();
                if(!visited[i])
                {
                    cout << mVexs[i] << " ";
                    visited[i] = 1;
                }

                int j;
                for (j = 0; j < mVexNum; j++)
                {
                //cout<<"此时i的值为" <<i<<",j的值为"<<j<< endl;
                if(!visited[j]&&mMatrix[i][j]!=0)
                {
                  //  cout << "放入" << endl;
                    stackForSearch.push(j);
                    break;
                }
                //getchar();
                }
                if(j==mVexNum&&!stackForSearch.empty()) 
                {
                    stackForSearch.pop();
                }
            
           
            }
        }
    }
    cout << endl;
}

void MapMatrix::DFSRsearch(int i,int * visited)
{
    
    int w;
    visited[i] = 1;
    cout << mVexs[i] << " ";
    
    for (int j = 0; j < mVexNum; j++)
    {
        w = mMatrix[i][j];
        /*if(i==1&&j==2)
        {
            cout<<"此时i的值为" <<i<<",j的值为"<<j<< endl;
            cout << mVexs[j] << endl;
            cout << w << endl;
            cout << "!!!" << endl;
            for (int l = 0; l < 5; l++)
                cout <<"l = "<<l<<":"<< visited[l] << endl;
            cout << mMatrix[i][j] << endl;
        }*/

        if(!visited[j]&&mMatrix[i][j]!=0)
        {
            //cout << mVexs[i] << "与" << mVexs[j] << "之间有连接," << endl;
            DFSRsearch(j, visited);
        }
    }
}

void MapMatrix::BFSsearch()
{
    int i;
    int visited[mVexNum];

    for (i = 0; i < mVexNum;i++)
    {
        visited[i] = 0;
    }
    cout << "进行BFS递归查找: ";
    for (i = 0; i < mVexNum;i++)
    {
        queue<int> queueForSearch;
        if(!visited[i])
        {
            
            queueForSearch.push(i);
            int w = i;
            while (!queueForSearch.empty())
            {
                //cout << "are you doing this?" << endl;
                w = queueForSearch.front();
                cout << mVexs[w] << " ";
                visited[w] = 1;
                queueForSearch.pop();
                int j;
                for (j = 0; j < mVexNum; j++)
                {
                    if(!visited[j]&&mMatrix[w][j])
                    {
                        queueForSearch.push(j);
                        
                    }
                }
                
            }
        }
    }
    cout << endl;
}

int main()
{
    //cout << "what??" << endl;
    MapMatrix *graph = new MapMatrix(5);
    
    graph->Insert("Map.txt");
    graph->DFSsearch();
    //cout << "what are you doing?" << endl;
    graph->BFSsearch();
    delete graph;
    return 0;
}